package com.kevin.Code.LinkNode;

/**
 * @author Vinlee Xiao
 * @Classname ReverseNodesInkGroup
 * @Description Leetcode 25 K个一组翻转链表 难度 困难 参考官方题解
 * @Date 2021/11/10 11:35
 * @Version 1.0
 */
public class ReverseNodesInkGroup {

    /**
     * 参考题解思路： 自己解题思路不正确
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {

        //如果为1,则直接返回原链表
        if (k == 1) {
            return head;
        }

        //哑结点 起辅助作用
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //前结点
        ListNode pre = dummy;

        while (head != null) {

            //用于记录每一次组的前一个结点
            ListNode tail = pre;

            for (int i = 0; i < k; i++) {
                tail = tail.next;
                //如果不足k,则直接返回结果
                if (tail == null) {
                    return dummy.next;
                }
            }
            //保留当前一组结点的下一个结点
            ListNode nextGroupHead = tail.next;
            //翻转链表
            ListNode[] listNodes = reverseNode(head, tail);
            head = listNodes[0];
            tail = listNodes[1];
            //
            pre.next = head;
            tail.next = nextGroupHead;
            pre = tail;
            head = tail.next;
        }

        return dummy.next;
    }

    /**
     * 用于反转结点
     *
     * @param head
     * @param tail
     * @return
     */
    public ListNode[] reverseNode(ListNode head, ListNode tail) {

        ListNode pre = tail.next;
        //移动结点
        ListNode move = head;

        while (pre != tail) {

            ListNode next = move.next;
            move.next = pre;
            pre = move;
            move = next;
        }

        //返回的尾结点作为头结点，头结点作为尾结点
        return new ListNode[]{tail, head};
    }

}
